package sort;
/*
* Offer45. 把数组排成最小的数
*
* x+y<y+x, 则表示x<y    喵喵喵
*
* */
public class Offer45minNumber {
    public String minNumber(int[] nums) {
        int n=nums.length;
        String[] str=new String[n];
        for (int i = 0; i < n; i++) {
            str[i]= String.valueOf(nums[i]);
        }
        quickSort(str,0,n-1);
        StringBuffer sb = new StringBuffer();
        for (String s : str) {
            sb.append(s);
        }
        return sb.toString();
    }

    private void quickSort(String[] str, int l, int r) {
        if(l>=r){
            return;
        }
        int i=l,j=r;
        while(i<j){
            while (i<j && (str[j]+str[l]).compareTo(str[l]+str[j])>=0){
                j--;
            }
            while (i<j && (str[i]+str[l]).compareTo(str[l]+str[i])<=0){
                i++;
            }
            swap(str,i,j);
        }
        swap(str,i,l);
        quickSort(str,l,i-1);
        quickSort(str,i+1,r);
    }

    private void swap(String[] str, int i, int j) {
        String tmp=str[i];
        str[i]=str[j];
        str[j]=tmp;
    }
}
